package org.example.myleet.trie;

import org.example.myleet.Utils.Assert;

import java.util.*;

public class TrieSolution {

    /**
     * 208【字典树】实现 Trie (前缀树)
     * 38 ms
     * 字典树
     */
    static class Trie208 {

        static class TrieNode208 {

            boolean end;

            Trie208.TrieNode208[] children;

            public TrieNode208(Trie208.TrieNode208[] children) {
                this.children = children;
                this.end = false;
            }
        }

        private Trie208.TrieNode208[] roots;

        /** Initialize your data structure here. */
        public Trie208() {
            roots = new Trie208.TrieNode208[26];
        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            Trie208.TrieNode208[] nodes = roots;
            int n = word.length() - 1;
            for (int i = 0; i < n; ++i) {
                char c = word.charAt(i);
                Trie208.TrieNode208 node = nodes[c - 'a'];
                //找到字符所在的node则继续寻找下一层，找不到就新建node
                if (node == null) {
                    Trie208.TrieNode208 newNode = new Trie208.TrieNode208(new Trie208.TrieNode208[26]);
                    nodes[c - 'a'] = newNode;
                    node = newNode;
                }
                nodes = node.children;
            }
            char c = word.charAt(n);
            Trie208.TrieNode208 node = nodes[c - 'a'];
            //单词最后一个字符所在的node要标记为结束位置，代表这个单词被字典树收录了
            if (node == null) {
                Trie208.TrieNode208 newNode = new Trie208.TrieNode208(new Trie208.TrieNode208[26]);
                newNode.end = true;
                nodes[c - 'a'] = newNode;
            } else {
                node.end = true;
            }
        }

        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            Trie208.TrieNode208[] nodes = roots;
            int n = word.length() - 1;
            for (int i = 0; i < n; ++i) {
                char c = word.charAt(i);
                Trie208.TrieNode208 node = nodes[c - 'a'];
                //找到字符所在的node则继续寻找下一层，找不到就代表找不到
                if (node == null) {
                    return false;
                }
                nodes = node.children;
            }
            char c = word.charAt(n);
            Trie208.TrieNode208 node = nodes[c - 'a'];
            //单词最后一个字符所在的node要看是不是结束位置，如果不是结束位置，说明其实字典树还没收录此单词
            if (node == null) {
                return false;
            } else {
                return node.end;
            }
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            Trie208.TrieNode208[] nodes = roots;
            int n = prefix.length();
            for (int i = 0; i < n; ++i) {
                char c = prefix.charAt(i);
                Trie208.TrieNode208 node = nodes[c - 'a'];
                //找到字符所在的node则继续寻找下一层，找不到就代表找不到。这其实是search的简化版
                if (node == null) {
                    return false;
                }
                nodes = node.children;
            }
            return true;
        }
    }

    /**
     * 211【字典树】添加与搜索单词 - 数据结构设计
     */
    static class WordDictionary {
        static class Trie {
            //每个节点有26个子节点的字典树
            public WordDictionary.Trie[] children;
            //记录是不是一个单词的结尾
            public boolean end;

            public Trie() {
                children = new WordDictionary.Trie[26];
                end = false;
            }
        }
        private WordDictionary.Trie root;
        public WordDictionary() {
            root = new WordDictionary.Trie();
        }
        public void addWord(String word) {
            //为字典树添加单词
            WordDictionary.Trie cur = root;
            for (int i = 0; i < word.length(); ++i) {
                //定位到单词中第i位的字母对应的子节点，如果是空的就新建这个子树，否则进入这个子树
                int idx = word.charAt(i) - 'a';
                if (null == cur.children[idx]) {
                    cur.children[idx] = new WordDictionary.Trie();
                }
                cur = cur.children[idx];
            }
            //到达单词末尾，记录这个节点是单词结尾
            cur.end = true;
        }
        public boolean search(String word) {
            //DFS的方法在字典树中搜索
            return dfs(word.toCharArray(), 0, root);
        }
        private boolean dfs(char[] charArr, int ithChar, WordDictionary.Trie cur) {
            if (ithChar >= charArr.length) {
                //到达搜索的字符末尾，如果是某个单词结尾，说明找到了，如果不是end就是找不到
                return cur.end;
            }
            char c = charArr[ithChar];
            if (c == '.') {
                //如果是'.'，需要对当前节点下的子树都进行搜索，只要其中一棵子树命中就算找到
                for (int i = 0; i < 26; ++i) {
                    if (null != cur.children[i]) {
                        if (dfs(charArr, ithChar + 1, cur.children[i])) {
                            return true;
                        }
                    }
                }
            } else {
                //如果是字母，则在对应的子树进行进一步搜索
                int i = c - 'a';
                if (null != cur.children[i]) {
                    return dfs(charArr, ithChar + 1, cur.children[i]);
                }
            }
            return false;
        }
    }

    /**
     * 421【位运算+字典树】数组中两个数的最大异或值
     */
    static class Trie421 {
        Trie421 left;
        Trie421 right;
    }
    private Trie421 root421 = new Trie421();
    public int findMaximumXOR(int[] nums) {
        int result = Integer.MIN_VALUE;
        for (int num : nums) {
            //加入字典树
            add421(num);
            //在字典树中检查
            result = Math.max(result, check421(num));
        }
        root421 = new Trie421();
        return result;
    }
    private void add421(int num) {
        Trie421 cur = root421;
        for (int i = 30; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (bit == 1) {
                if (cur.right == null) {
                    cur.right = new Trie421();
                }
                cur = cur.right;
            } else {
                if (cur.left == null) {
                    cur.left = new Trie421();
                }
                cur = cur.left;
            }
        }
    }
    private int check421(int num) {
        int result = 0;
        Trie421 cur = root421;
        for (int i = 30; i >= 0; --i) {
            int bit = (num >> i) & 1;
            if (bit == 1) {
                if (cur.left != null) {
                    //说明可以在这一位通过取反使得这一位为1
                    result = (result << 1) + 1;
                    cur = cur.left;
                } else {
                    //说明不可以在这一位通过取反，使得这一位只能为0
                    result = result << 1;
                    cur = cur.right;
                }
            } else {
                if (cur.right != null) {
                    result = (result << 1) + 1;
                    cur = cur.right;
                } else {
                    result = result << 1;
                    cur = cur.left;
                }
            }
        }
        return result;
    }

    //1032
    static class StreamChecker {

        private TrieTree trieTree;

        private List<Character> letterQueue;

        public StreamChecker(String[] words) {
            trieTree = new TrieTree(26);
            for (String word : words) {
                //单词逆序，并添加到字典树中
                char[] w = word.toCharArray();
                int l = 0, r = w.length - 1;
                while (l < r) {
                    char t = w[r];
                    w[r] = w[l];
                    w[l] = t;
                    ++l;
                    --r;
                }
                trieTree.addWord(w);
            }
            //链表可以让字母插入更高效
            letterQueue = new LinkedList<>();
        }

        public boolean query(char letter) {
            letterQueue.add(0, letter);
            trieTree.resetDig();
            for (Character c : letterQueue) {
                //从队列头开始往前匹配单词
                int digResult = trieTree.dig(c);
                if (TrieTree.FOUND == digResult) {
                    return true;
                }
                if (TrieTree.NOT_FOUND == digResult) {
                    return false;
                }
            }
            return false;
        }
    }

    //p1233
    private static class Trie1233 {
        Map<String, Trie1233> children;
        String dirName;
        boolean end;
        public Trie1233(String dirName) {
            this.dirName = dirName;
            end = false;
            children = new HashMap<>();
        }
        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Trie1233{");
            sb.append("children=").append(children.size() > 0);
            sb.append(", dirName='").append(dirName).append('\'');
            sb.append(", end=").append(end);
            sb.append('}');
            return sb.toString();
        }
    }
    public List<String> removeSubfolders(String[] folder) {
        int[][] depths = new int[folder.length][2];
        for (int i = 0; i < folder.length; ++i) {
            int depth = 0;
            for (int j = 0; j < folder[i].length(); ++j) {
                char ch = folder[i].charAt(j);
                if (ch == '/') {
                    ++depth;
                }
            }
            depths[i][0] = i;
            depths[i][1] = depth;
        }
        Arrays.sort(depths, Comparator.comparingInt(o -> o[1]));
        Set<Integer> removeIndexes = new HashSet<>();
        Trie1233 root = new Trie1233("");
        outer:
        for (int i = 0; i < depths.length; ++i) {
            String f = folder[depths[i][0]];
            Trie1233 cur = root;
            int a = 0;
            int b = f.indexOf("/", a + 1);
            while (b > 0) {
                String dirName = f.substring(a + 1, b);
                if (cur.children.containsKey(dirName)) {
                    cur = cur.children.get(dirName);
                    if (cur.end) {
                        removeIndexes.add(depths[i][0]);
                        continue outer;
                    }
                } else {
                    Trie1233 child = new Trie1233(dirName);
                    cur.children.put(dirName, child);
                    cur = child;
                }
                a = b;
                b = f.indexOf("/", a + 1);
            }
            String dirName = f.substring(a + 1);
            Trie1233 child = cur.children.get(dirName);
            if (null == child) {
                child = new Trie1233(dirName);
                cur.children.put(dirName, child);
            }
            child.end = true;
        }
        List<String> answer = new ArrayList<>(removeIndexes.size());
        for (int i = 0; i < folder.length; ++i) {
            if (!removeIndexes.contains(i)) {
                answer.add(folder[i]);
            }
        }
        return answer;
    }

    //p1803
    public int countPairs(int[] nums, int low, int high) {
        return f1803(nums, high) - f1803(nums, low - 1);
    }
    // 字典树的根节点
    private Trie1803 root1803 = null;
    // 最高位的二进制位编号为 14
    private static final int HIGH_BIT_1803 = 14;
    private void add1803(int num) {
        Trie1803 cur = root1803;
        for (int i = HIGH_BIT_1803; i >= 0; i--) {
            int idx = (num >> i) & 1;
            if (null == cur.son[idx]) {
                cur.son[idx] = new Trie1803();
            }
            cur = cur.son[idx];
            ++cur.sum;
        }
    }
    private int f1803(int[] nums, int x) {
        //每次计算f(x)时重新构造字典树
        root1803 = new Trie1803();
        int res = 0;
        for (int j = 1; j < nums.length; j++) {
            //每次计算有多少个nums[i]和nums[j]异或能够小于x，先添加nums[i]，然后再按nums[j]查找结果并累加
            int i = j - 1;
            add1803(nums[i]);
            res += get1803(nums[j], x);
        }
        return res;
    }
    public int get1803(int numJ, int x) {
        //每次get相当于在字典树中查找满足前面已经添加的nums[i]
        Trie1803 cur = root1803;
        int sum = 0;
        for (int k = HIGH_BIT_1803; k >= 0; k--) {
            int r = (numJ >> k) & 1;
            if (((x >> k) & 1) != 0) {
                //x对应的位置是1，此时如果对应前缀的nums[j]存在，则肯定能满足nums[i]和nums[j]异或结果小于x
                if (cur.son[r] != null) {
                    sum += cur.son[r].sum;
                }
                //r^1子节点保证了路径上的数值与num[i]做异或后，前缀与x相同，若r^1子节点不存在，则无需继续查找，返回结果
                if (cur.son[r ^ 1] == null) {
                    return sum;
                }
                //存在r^1子节点，继续深入查找
                cur = cur.son[r ^ 1];
            } else {
                //x对应的位置是0，若对应前缀的nums[j]不存在，则不用继续深入查找
                if (cur.son[r] == null) {
                    return sum;
                }
                //存在r子节点，保证路径上的数值与num[i]做异或后前缀与x相同，深入查找
                cur = cur.son[r];
            }
        }
        sum += cur.sum;
        return sum;
    }
    static class Trie1803 {
        // son[0] 表示左子树，son[1] 表示右子树
        Trie1803[] son = new Trie1803[2];
        int sum;

        public Trie1803() {
            sum = 0;
        }
    }

    /**
     * 3291【字典树】形成目标字符串需要的最少字符串数 I
     */
    static class TrieNode3291 {
        TrieNode3291[] children;
        public TrieNode3291() {
            children = new TrieNode3291[26];
        }
    }
    public int minValidStrings(String[] words, String target) {
        int INF = 0x3f3f3f3f;
        //构建字典树
        TrieNode3291 root = new TrieNode3291();
        for (String word : words) {
            TrieNode3291[] children = root.children;
            for (int i = 0; i < word.length(); ++i) {
                char c = word.charAt(i);
                int idx = c - 'a';
                if (null == children[idx]) {
                    children[idx] = new TrieNode3291();
                }
                children = children[idx].children;
            }
        }
        int n = target.length();
        int[] dp = new int[n + 1];
        Arrays.fill(dp, INF);
        dp[n] = 0;
        for (int l = n - 1; l >= 0; --l) {
            TrieNode3291 child = root;
            for (int r = l; r < n; ++r) {
                //验证l...r之间是否存在前缀可以匹配
                child = child.children[target.charAt(r) - 'a'];
                if (null == child) break;
                dp[l] = Math.min(dp[l], dp[r + 1] + 1);
            }
        }
        if (dp[0] == INF) return -1;
        return dp[0];
    }

    public static void main(String[] args) {
        TrieSolution solution = new TrieSolution();
        Assert.isTrue(3 == solution.minValidStrings(new String[]{"abc","aaaaa","bcdef"}, "aabcdabc"));
    }
}
